In many computing systems that implement caching, a cache supports multiple cache levels (e.g., L1, L2, L3, etc.). Many cache systems spill from one cache level to another cache level, when the data in the cache is measured or deemed to be less likely to be retrieved again (e.g., due to age in the cache, or due to being already processed, or due to any other reason). Some caching systems use RAM as the first tier of cache and solid-state devices as the next tier. Often a caching system is implemented in the context of computing system hardware that has a natural size of an item in cache. For example, an instruction cache might exhibit a natural size for such an instruction cache entry that is the same size as an instruction. Or, for example, a content cache that brings in cache entries from a block-oriented device such as a hard disk drive (HDD) or a solid-state drive (SSD), where the natural size for a cache entry that is the same size as a block from the block-oriented device. In some cases, all or substantially all of the data found within the bounds of a cached item are used in processing (e.g., the entire instruction, or all bytes of a block from a block-oriented device). However, there are many cases where a single block is composed of many smaller units of individually addressable data items. For example, consider a series of names (e.g., user names, subscriber names, etc.) that are stored end-to-end in as many block as are needed to store the entire series. In such scenarios involving smaller units of individually-addressable data items, even a retrieval (e.g., from the block-oriented device) of just one of the smaller individually-addressable data items would necessitate retrieval of the entire block due to the natural block size of the block-oriented device. The entire block has been retrieved, and the caching system will store the entire block—even though only one unit of the smaller individually-addressable data items has been addressed by the data requestor. When such occurrences are rare, the efficiency impacts to a caching system that inserts and manages such partially-useful blocks is small, however as such occurrences increase in number or ratio, caching the entire-block-for-just-one-small-entry regime becomes commensurately wasteful.
Unfortunately, the wastefulness as just described is exacerbated when the caching system spills over into a block-oriented device such as a solid-state device. As an example, storing a user name of (for example) size=40 bytes would spill over into an SSD block of 4K bytes, which would calculate to a use factor of less than 1% (i.e., >99% wasted space). Legacy approaches to avoid such waste have included evicting small cache items without implementing SSD spillover, however, this often defeats the reason for caching the data item in the first place (e.g., a next access would result in a cache MISS and another retrieval). Other legacy approaches prospectively retain smaller individually-addressable data items in higher levels of cache for longer periods of time than other entries (e.g., without spillover to lower levels of SSD cache), however this technique results in filling up the higher levels of cache with data that might or might not be accessed again—thus using higher-level cache resources that could be used for more frequently accessed data items. Still other caching systems have increased the size of spillover SSD, however, this merely adds to a system's cost without addressing the wastefulness. What is needed is a technique or techniques that facilitate cache spillover of small data items into SSD without incurring the wastefulness as heretofore described.
What is needed is a technique or techniques to improve over legacy approaches.